package leetcode.problems;

/**
 * _0328Sum of Left Leaves
 * 左侧叶子节点的和
 * Created by gmwang on 2018/3/23
 */
public class _0328SumofLeftLeaves {
    /**
     * Find the sum of all left leaves in a given binary tree.
     * Example:
     * <p>
         *    3
         * /   \
         * 9    20
          /  \  /  \
         15   7 15   7
     * <p>
     * There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
     *
     * @param
     */
    /**
     * 思路：
     * 是否是左侧叶子结点，如果是就加。
     * 不是，就对左侧的结点继续找叶子结点。
     * 再对右侧的结点求和。
     * 递归调用方法。
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        int ans = 0;
        if(root.left != null) {
            if(root.left.left == null && root.left.right == null) ans += root.left.val;
            else ans += sumOfLeftLeaves(root.left);
        }
        ans += sumOfLeftLeaves(root.right);
        return ans;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode rootL = new TreeNode(9);
        TreeNode rootR = new TreeNode(20);
        root.left = rootL;
        root.right = rootR;
        TreeNode rootRL = new TreeNode(15);
        TreeNode rootRR = new TreeNode(7);
        rootR.left = rootRL;
        rootR.right = rootRR;
//        TreeNode rootLL = new TreeNode(15);
//        TreeNode rootLR = new TreeNode(7);
//        rootL.left = rootLL;
//        rootL.right = rootLR;
        System.out.println(sumOfLeftLeaves(root));
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
